package leetcode.code2171;

import java.util.Arrays;

//SolutionTest
public class Solution {

	public long minimumRemoval(int[] beans) {
		Arrays.sort(beans);
		int len = beans.length;
		long[] sums = this.sums(beans);
		long ans = Long.MAX_VALUE;
		int l = 0;
		for (int r = 0; r < len; r++) {
			if (beans[r] != beans[l]) {
				long curAns = this.sumsLR(sums, r, len - 1) - (long) (len - r) * beans[l] + this.sumsLR(sums, 0, l - 1);
				if (curAns < ans) {
					ans = curAns;
				}
				l = r;
			}
		}
		long curAns = this.sumsLR(sums, 0, l - 1);
		if (curAns < ans) {
			ans = curAns;
		}
		return ans == Long.MAX_VALUE ? 0 : ans;
	}

	public long[] sums(int[] nums) {
		int len = nums.length;
		long[] sums = new long[len];
		sums[0] = nums[0];
		for (int i = 1; i < len; i++) {
			sums[i] = sums[i - 1] + nums[i];
		}
		return sums;
	}

	public long sumsLR(long[] sums, int L, int R) {
		return L == 0 ? R < 0 ? 0 : sums[R] : sums[R] - sums[L - 1];
	}

}
